package cn.com.yang.datastruct.sort;

import java.util.Arrays;

/**
 * 希尔排序，在插入排序的基础上增加一个间距
 */
public class XierSort {

    public static void sort(int[] data){
        System.out.println("排序前："+ Arrays.toString(data));
        int ourter;
        int inner;
        int temp;
        int len = data.length;
        // 一共三种间隔
        int step =1;
        while (step<=len/3){
            step = step * 3 +1;
        }
//        for (step = (int) (len/2.2); step>0; step = (int) (step/2.2)){
//            for (ourter=step;ourter<len;ourter++){
//                inner =ourter;
//                temp=data[ourter];
//                while (inner-step>=0 && temp<data[inner-step]){
//                    data[inner] =data[inner-step];
//                    inner = inner-step;
//                }
//                data[inner] =temp;
//            }
//            System.out.println("间隔数是："+ step+"时，排序是："+Arrays.toString(data));
//        }

        while (step >0){
            for (ourter=step;ourter<len;ourter++){
                inner =ourter;
                temp=data[ourter];
                while (inner-step>=0 && temp<data[inner-step]){
                    data[inner] =data[inner-step];
                    inner = inner-step;
                }
                data[inner] =temp;
            }
            System.out.println("间隔数是："+ step+"时，排序是："+Arrays.toString(data));
            step =step-1;
        }
        System.out.println("排序后："+Arrays.toString(data));
    }
}
